home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / documents / RFC / rfc896.txt < prev    next >
Text File  |  1994-08-01  |  27KB  |  513 lines

  1.  
  2.  
  3. Network Working Group                                  John Nagle
  4. Request For Comments:  896                         6 January 1984
  5.                     Ford Aerospace and Communications Corporation
  6.  
  7.            Congestion Control in IP/TCP Internetworks
  8.  
  9. This memo discusses some aspects of congestion control in  IP/TCP
  10. Internetworks.   It  is intended to stimulate thought and further
  11. discussion of this topic.   While some specific  suggestions  are
  12. made for improved congestion  control  implementation,  this memo
  13. does not specify any standards.
  14.  
  15.                           Introduction
  16.  
  17. Congestion control is a recognized problem in  complex  networks.
  18. We have discovered that the Department of Defense's Internet Pro-
  19. tocol (IP) , a pure datagram protocol, and  Transmission  Control
  20. Protocol  (TCP),  a transport layer protocol, when used together,
  21. are subject to unusual congestion problems caused by interactions
  22. between  the  transport  and  datagram layers.  In particular, IP
  23. gateways are vulnerable to a phenomenon we call  "congestion col-
  24. lapse",  especially when such gateways connect networks of widely
  25. different bandwidth.  We have developed  solutions  that  prevent
  26. congestion collapse.
  27.  
  28. These problems are not generally recognized because these  proto-
  29. cols  are used most often on networks built on top of ARPANET IMP
  30. technology.  ARPANET IMP based networks traditionally  have  uni-
  31. form  bandwidth and identical switching nodes, and are sized with
  32. substantial excess capacity.  This excess capacity, and the abil-
  33. ity  of the IMP system to throttle the transmissions of hosts has
  34. for most IP / TCP hosts and  networks  been  adequate  to  handle
  35. congestion.  With the recent split of the ARPANET into two inter-
  36. connected networks and the growth of other networks with  differ-
  37. ing properties connected to the ARPANET, however, reliance on the
  38. benign properties of the IMP system is no longer enough to  allow
  39. hosts  to  communicate rapidly and reliably. Improved handling of
  40. congestion is now  mandatory  for  successful  network  operation
  41. under load.
  42.  
  43. Ford Aerospace and Communications  Corporation,  and  its  parent
  44. company,  Ford  Motor  Company,  operate  the only private IP/TCP
  45. long-haul network in existence today.  This network connects four
  46. facilities  (one  in Michigan, two in California, and one in Eng-
  47. land) some with extensive local networks.  This net is cross-tied
  48. to  the  ARPANET  but  uses  its  own long-haul circuits; traffic
  49. between Ford  facilities  flows  over  private  leased  circuits,
  50. including  a  leased  transatlantic  satellite  connection.   All
  51. switching nodes are pure IP datagram switches  with  no  node-to-
  52. node  flow  control, and all hosts run software either written or
  53. heavily modified by Ford or Ford Aerospace.  Bandwidth  of  links
  54. in  this  network varies widely, from 1200 to 10,000,000 bits per
  55. second.  In general, we have not been able to afford  the  luxury
  56. of excess long-haul bandwidth that the ARPANET possesses, and our
  57. long-haul links are heavily loaded during peak periods.   Transit
  58. times of several seconds are thus common in our network.
  59.  
  60.  
  61. RFC 896    Congestion Control in IP/TCP Internetworks      1/6/84
  62.  
  63.  
  64. Because of our pure datagram orientation, heavy loading, and wide
  65. variation  in  bandwidth,  we have had to solve problems that the
  66. ARPANET / MILNET community is just beginning to  recognize.   Our
  67. network is sensitive to suboptimal behavior by host TCP implemen-
  68. tations, both on and off our own net.  We have devoted  consider-
  69. able  effort  to examining TCP behavior under various conditions,
  70. and have solved some widely  prevalent  problems  with  TCP.   We
  71. present  here  two problems and their solutions.  Many TCP imple-
  72. mentations have these problems; if throughput is worse through an
  73. ARPANET  /  MILNET  gateway  for  a given TCP implementation than
  74. throughput across a single net, there is a high probability  that
  75. the TCP implementation has one or both of these problems.
  76.  
  77.                        Congestion collapse
  78.  
  79. Before we proceed with a discussion of the two specific  problems
  80. and  their  solutions,  a  description of what happens when these
  81. problems are not addressed is in order.  In heavily  loaded  pure
  82. datagram  networks  with  end to end retransmission, as switching
  83. nodes become congested, the  round  trip  time  through  the  net
  84. increases  and  the  count of datagrams in transit within the net
  85. also increases.  This is normal behavior under load.  As long  as
  86. there is only one copy of each datagram in transit, congestion is
  87. under  control.   Once  retransmission  of  datagrams   not   yet
  88. delivered begins, there is potential for serious trouble.
  89.  
  90. Host TCP  implementations  are  expected  to  retransmit  packets
  91. several times at increasing time intervals until some upper limit
  92. on the retransmit interval is reached.  Normally, this  mechanism
  93. is  enough to prevent serious congestion problems.  Even with the
  94. better adaptive host retransmission algorithms, though, a  sudden
  95. load on the net can cause the round-trip time to rise faster than
  96. the sending hosts measurements of round-trip time can be updated.
  97. Such  a  load  occurs  when  a  new  bulk  transfer,  such a file
  98. transfer, begins and starts filling a large window.   Should  the
  99. round-trip  time  exceed  the maximum retransmission interval for
  100. any host, that host will begin to introduce more and more  copies
  101. of  the same datagrams into the net.  The network is now in seri-
  102. ous trouble.  Eventually all available buffers in  the  switching
  103. nodes  will  be full and packets must be dropped.  The round-trip
  104. time for packets that are delivered is now at its maximum.  Hosts
  105. are  sending  each packet several times, and eventually some copy
  106. of each packet arrives at its destination.   This  is  congestion
  107. collapse.
  108.  
  109. This condition is stable.  Once the  saturation  point  has  been
  110. reached,  if the algorithm for selecting packets to be dropped is
  111. fair, the network will continue to operate in a  degraded  condi-
  112. tion.   In  this  condition  every  packet  is  being transmitted
  113. several times and throughput is reduced to a  small  fraction  of
  114. normal.   We  have pushed our network into this condition experi-
  115. mentally and observed its stability.  It is possible  for  round-
  116. trip  time to become so large that connections are broken because
  117.  
  118.  
  119. RFC 896    Congestion Control in IP/TCP Internetworks      1/6/84
  120.  
  121.  
  122. the hosts involved time out.
  123.  
  124. Congestion collapse and pathological congestion are not  normally
  125. seen  in  the ARPANET / MILNET system because these networks have
  126. substantial excess  capacity.   Where  connections  do  not  pass
  127. through IP gateways, the IMP-to host flow control mechanisms usu-
  128. ally prevent congestion collapse, especially since TCP  implemen-
  129. tations  tend  to be well adjusted for the time constants associ-
  130. ated with the pure ARPANET case.  However, other than ICMP Source
  131. Quench  messages,  nothing fundamentally prevents congestion col-
  132. lapse when TCP is run over the ARPANET / MILNET and  packets  are
  133. being  dropped  at  gateways.  Worth  noting is that a few badly-
  134. behaved hosts can by themselves congest the gateways and  prevent
  135. other  hosts from passing traffic.  We have observed this problem
  136. repeatedly with certain hosts (with whose administrators we  have
  137. communicated privately) on the ARPANET.
  138.  
  139. Adding additional memory to the gateways will not solve the prob-
  140. lem.   The  more  memory  added, the longer round-trip times must
  141. become before packets are dropped.  Thus, the onset of congestion
  142. collapse  will be delayed but when collapse occurs an even larger
  143. fraction of the  packets  in  the  net  will  be  duplicates  and
  144. throughput will be even worse.
  145.  
  146.                         The two problems
  147.  
  148. Two key problems with the engineering of TCP implementations have
  149. been  observed;  we  call  these the small-packet problem and the
  150. source-quench problem.  The second is being addressed by  several
  151. implementors; the first is generally believed (incorrectly) to be
  152. solved.  We have discovered that once  the  small-packet  problem
  153. has  been  solved,  the  source-quench  problem becomes much more
  154. tractable.  We thus present  the  small-packet  problem  and  our
  155. solution to it first.
  156.  
  157.                     The small-packet problem
  158.  
  159. There is a special problem associated with small  packets.   When
  160. TCP  is  used  for  the transmission of single-character messages
  161. originating at a keyboard, the typical result  is  that  41  byte
  162. packets  (one  byte  of data, 40 bytes of header) are transmitted
  163. for each byte of useful data.  This 4000%  overhead  is  annoying
  164. but tolerable on lightly loaded networks.  On heavily loaded net-
  165. works, however, the congestion resulting from this  overhead  can
  166. result  in  lost datagrams and retransmissions, as well as exces-
  167. sive propagation time caused by congestion in switching nodes and
  168. gateways.   In practice, throughput may drop so low that TCP con-
  169. nections are aborted.
  170.  
  171. This classic problem is well-known and was first addressed in the
  172. Tymnet network in the late 1960s.  The solution used there was to
  173. impose a limit on the count of datagrams generated per unit time.
  174. This limit was enforced by delaying transmission of small packets
  175.  
  176.  
  177. RFC 896    Congestion Control in IP/TCP Internetworks      1/6/84
  178.  
  179.  
  180. until a short (200-500ms) time had elapsed, in hope that  another
  181. character  or two would become available for addition to the same
  182. packet before the  timer  ran  out.   An  additional  feature  to
  183. enhance  user  acceptability was to inhibit the time delay when a
  184. control character, such as a carriage return, was received.
  185.  
  186. This technique has been used in NCP Telnet, X.25  PADs,  and  TCP
  187. Telnet. It has the advantage of being well-understood, and is not
  188. too difficult to implement.  Its flaw is that it is hard to  come
  189. up  with  a  time limit that will satisfy everyone.  A time limit
  190. short enough to provide highly responsive service over a 10M bits
  191. per  second Ethernet will be too short to prevent congestion col-
  192. lapse over a heavily loaded net with  a  five  second  round-trip
  193. time;  and  conversely,  a  time  limit long enough to handle the
  194. heavily loaded net will produce frustrated users on the Ethernet.
  195.  
  196.             The solution to the small-packet problem
  197.  
  198. Clearly an adaptive approach is desirable.  One  would  expect  a
  199. proposal  for  an  adaptive  inter-packet time limit based on the
  200. round-trip delay observed by TCP.  While such a  mechanism  could
  201. certainly  be  implemented,  it  is  unnecessary.   A  simple and
  202. elegant solution has been discovered.
  203.  
  204. The solution is to inhibit the sending of new TCP  segments  when
  205. new  outgoing  data  arrives  from  the  user  if  any previously
  206. transmitted data on the connection remains unacknowledged.   This
  207. inhibition  is  to be unconditional; no timers, tests for size of
  208. data received, or other conditions are required.   Implementation
  209. typically requires one or two lines inside a TCP program.
  210.  
  211. At first glance, this solution seems to imply drastic changes  in
  212. the  behavior of TCP.  This is not so.  It all works out right in
  213. the end.  Let us see why this is so.
  214.  
  215. When a user process writes to a TCP connection, TCP receives some
  216. data.   It  may  hold  that data for future sending or may send a
  217. packet immediately.  If it refrains from  sending  now,  it  will
  218. typically send the data later when an incoming packet arrives and
  219. changes the state of the system.  The state changes in one of two
  220. ways;  the incoming packet acknowledges old data the distant host
  221. has received, or announces the availability of  buffer  space  in
  222. the  distant  host  for  new  data.  (This last is referred to as
  223. "updating the window").    Each time data arrives  on  a  connec-
  224. tion,  TCP must reexamine its current state and perhaps send some
  225. packets out.  Thus, when we omit sending data on arrival from the
  226. user,  we  are  simply  deferring its transmission until the next
  227. message arrives from the distant host.   A  message  must  always
  228. arrive soon unless the connection was previously idle or communi-
  229. cations with the other end have been lost.  In  the  first  case,
  230. the  idle  connection,  our  scheme will result in a packet being
  231. sent whenever the user writes to the TCP connection.  Thus we  do
  232. not  deadlock  in  the idle condition.  In the second case, where
  233.  
  234.  
  235. RFC 896    Congestion Control in IP/TCP Internetworks      1/6/84
  236.  
  237.  
  238. the distant host has failed, sending more data is futile  anyway.
  239. Note  that we have done nothing to inhibit normal TCP retransmis-
  240. sion logic, so lost messages are not a problem.
  241.  
  242. Examination of the behavior of this scheme under  various  condi-
  243. tions  demonstrates  that the scheme does work in all cases.  The
  244. first case to examine is the one we wanted to solve, that of  the
  245. character-oriented  Telnet  connection.   Let us suppose that the
  246. user is sending TCP a new character every  200ms,  and  that  the
  247. connection  is  via  an Ethernet with a round-trip time including
  248. software processing of 50ms.  Without any  mechanism  to  prevent
  249. small-packet congestion, one packet will be sent for each charac-
  250. ter, and response will be optimal.  Overhead will be  4000%,  but
  251. this  is  acceptable  on  an Ethernet.  The classic timer scheme,
  252. with a limit of 2 packets per second, will  cause  two  or  three
  253. characters to be sent per packet.  Response will thus be degraded
  254. even though on a high-bandwidth  Ethernet  this  is  unnecessary.
  255. Overhead  will  drop  to  1500%, but on an Ethernet this is a bad
  256. tradeoff.  With our scheme, every character the user  types  will
  257. find  TCP with an idle connection, and the character will be sent
  258. at once, just as in the no-control case.  The user  will  see  no
  259. visible  delay.   Thus,  our  scheme  performs as well as the no-
  260. control scheme and provides better responsiveness than the  timer
  261. scheme.
  262.  
  263. The second case to examine is the same Telnet  test  but  over  a
  264. long-haul  link  with  a  5-second  round trip time.  Without any
  265. mechanism to prevent  small-packet  congestion,  25  new  packets
  266. would be sent in 5 seconds.* Overhead here is  4000%.   With  the
  267. classic timer scheme, and the same limit of 2 packets per second,
  268. there would still be 10 packets outstanding and  contributing  to
  269. congestion.  Round-trip time will not be improved by sending many
  270. packets, of course; in general it will be worse since the packets
  271. will  contend  for line time.  Overhead now drops to 1500%.  With
  272. our scheme, however, the first character from the user would find
  273. an  idle  TCP connection and would be sent immediately.  The next
  274. 24 characters, arriving from the user at 200ms  intervals,  would
  275. be  held  pending  a  message from the distant host.  When an ACK
  276. arrived for the first packet at the end of 5  seconds,  a  single
  277. packet  with  the 24 queued characters would be sent.  Our scheme
  278. thus results in an overhead reduction to 320% with no penalty  in
  279. response  time.   Response time will usually be improved with our
  280. scheme because packet overhead is reduced, here by  a  factor  of
  281. 4.7 over the classic timer scheme.  Congestion will be reduced by
  282. this factor and round-trip delay will decrease sharply.  For this
  283. ________
  284.   * This problem is not seen in the pure ARPANET case because the
  285.     IMPs will block the host when the count of packets
  286.     outstanding becomes excessive, but in the case where a pure
  287.     datagram local net (such as an Ethernet) or a pure datagram
  288.     gateway (such as an ARPANET / MILNET gateway) is involved, it
  289.     is possible to have large numbers of tiny packets
  290.     outstanding.
  291.  
  292.  
  293. RFC 896    Congestion Control in IP/TCP Internetworks      1/6/84
  294.  
  295.  
  296. case, our scheme has a striking  advantage  over  either  of  the
  297. other approaches.
  298.  
  299. We use our scheme for all TCP connections, not just  Telnet  con-
  300. nections.   Let us see what happens for a file transfer data con-
  301. nection using our technique. The two extreme cases will again  be
  302. considered.
  303.  
  304. As before, we first consider the Ethernet case.  The user is  now
  305. writing data to TCP in 512 byte blocks as fast as TCP will accept
  306. them.  The user's first write to TCP will start things going; our
  307. first  datagram  will  be  512+40  bytes  or 552 bytes long.  The
  308. user's second write to TCP will not cause a send but  will  cause
  309. the  block  to  be buffered.  Assume that the user fills up TCP's
  310. outgoing buffer area before the first ACK comes back.  Then  when
  311. the  ACK  comes in, all queued data up to the window size will be
  312. sent.  From then on, the window will be kept full,  as  each  ACK
  313. initiates  a  sending  cycle  and queued data is sent out.  Thus,
  314. after a one round-trip time initial period when only one block is
  315. sent,  our  scheme  settles down into a maximum-throughput condi-
  316. tion.  The delay in startup is only 50ms on the Ethernet, so  the
  317. startup  transient  is  insignificant.  All three schemes provide
  318. equivalent performance for this case.
  319.  
  320. Finally, let us look at a file transfer over the  5-second  round
  321. trip  time connection.  Again, only one packet will be sent until
  322. the first ACK comes back; the window will then be filled and kept
  323. full.   Since the round-trip time is 5 seconds, only 512 bytes of
  324. data are transmitted in the first 5 seconds.  Assuming a 2K  win-
  325. dow,  once  the first ACK comes in, 2K of data will be sent and a
  326. steady rate of 2K per 5 seconds will  be  maintained  thereafter.
  327. Only  for  this  case is our scheme inferior to the timer scheme,
  328. and the difference is only in the startup transient; steady-state
  329. throughput  is  identical.  The naive scheme and the timer scheme
  330. would both take 250 seconds to transmit a 100K  byte  file  under
  331. the  above  conditions  and  our scheme would take 254 seconds, a
  332. difference of 1.6%.
  333.  
  334. Thus, for all cases examined, our scheme provides at least 98% of
  335. the  performance  of  both other schemes, and provides a dramatic
  336. improvement in Telnet performance over paths with long round trip
  337. times.   We  use  our  scheme  in  the  Ford  Aerospace  Software
  338. Engineering Network, and are able to run screen editors over Eth-
  339. ernet and talk to distant TOPS-20 hosts with improved performance
  340. in both cases.
  341.  
  342.                   Congestion control with ICMP
  343.  
  344. Having solved the small-packet congestion problem and with it the
  345. problem  of excessive small-packet congestion within our own net-
  346. work, we turned our attention to the problem of  general  conges-
  347. tion  control.   Since  our  own network is pure datagram with no
  348. node-to-node flow control, the only  mechanism  available  to  us
  349.  
  350.  
  351. RFC 896    Congestion Control in IP/TCP Internetworks      1/6/84
  352.  
  353.  
  354. under  the  IP standard was the ICMP Source Quench message.  With
  355. careful handling,  we  find  this  adequate  to  prevent  serious
  356. congestion problems.  We do find it necessary to be careful about
  357. the behavior of our hosts and switching  nodes  regarding  Source
  358. Quench messages.
  359.  
  360.                When to send an ICMP Source Quench
  361.  
  362. The present ICMP standard* specifies that an ICMP  Source  Quench
  363. message  should  be  sent whenever a packet is dropped, and addi-
  364. tionally may be sent when a gateway finds itself  becoming  short
  365. of  resources.   There is some ambiguity here but clearly it is a
  366. violation of the standard to drop a  packet  without  sending  an
  367. ICMP message.
  368.  
  369. Our basic assumption is that packets ought not to be dropped dur-
  370. ing  normal  network  operation.   We  therefore want to throttle
  371. senders back before they overload switching nodes  and  gateways.
  372. All  our  switching  nodes  send ICMP Source Quench messages well
  373. before buffer space is exhausted; they do not wait  until  it  is
  374. necessary to drop a message before sending an ICMP Source Quench.
  375. As demonstrated in our  analysis  of  the  small-packet  problem,
  376. merely  providing  large  amounts of buffering is not a solution.
  377. In general, our experience is that Source Quench should  be  sent
  378. when  about  half  the  buffering space is exhausted; this is not
  379. based on extensive experimentation but appears to be a reasonable
  380. engineering  decision.   One  could  argue for an adaptive scheme
  381. that adjusted the quench generation  threshold  based  on  recent
  382. experience; we have not found this necessary as yet.
  383.  
  384. There exist other gateway implementations  that  generate  Source
  385. Quenches  only after more than one packet has been discarded.  We
  386. consider this approach undesirable since any system for  control-
  387. ling congestion based on the discarding of packets is wasteful of
  388. bandwidth and may be susceptible  to  congestion  collapse  under
  389. heavy  load.   Our understanding is that the decision to generate
  390. Source Quenches with great reluctance stems from a fear that ack-
  391. nowledge  traffic  will  be quenched and that this will result in
  392. connection failure.  As will be shown below, appropriate handling
  393. of  Source  Quench in host implementations eliminates this possi-
  394. bility.
  395.  
  396.         What to do when an ICMP Source Quench is received
  397.  
  398. We inform TCP or any other  protocol  at  that  layer  when  ICMP
  399. receives  a Source Quench.  The basic action of our TCP implemen-
  400. tations is to reduce the amount of data  outstanding  on  connec-
  401. tions to the host mentioned in the Source Quench. This control is
  402. ________
  403.   * ARPANET RFC 792 is the present standard.  We are advised by
  404.     the Defense Communications Agency that the description of
  405.     ICMP in MIL-STD-1777 is incomplete and will be deleted from
  406.     future revision of that standard.
  407.  
  408.  
  409. RFC 896    Congestion Control in IP/TCP Internetworks      1/6/84
  410.  
  411.  
  412. applied by causing the sending TCP to behave as  if  the  distant
  413. host's  window  size  has been reduced.  Our first implementation
  414. was simplistic but effective;  once  a  Source  Quench  has  been
  415. received  our  TCP behaves as if the window size is zero whenever
  416. the window isn't  empty.   This  behavior  continues  until  some
  417. number  (at  present 10) of ACKs have been received, at that time
  418. TCP returns to normal operation.* David Mills  of  Linkabit  Cor-
  419. poration  has  since  implemented  a  similar  but more elaborate
  420. throttle on the count of outstanding packets in his DCN  systems.
  421. The  additional  sophistication seems to produce a modest gain in
  422. throughput, but we have not made formal tests.  Both  implementa-
  423. tions effectively prevent congestion collapse in switching nodes.
  424.  
  425. Source Quench thus has the effect of limiting the connection to a
  426. limited number (perhaps one) of outstanding messages.  Thus, com-
  427. munication can continue but at a reduced rate,  that  is  exactly
  428. the effect desired.
  429.  
  430. This scheme has the important property that Source Quench doesn't
  431. inhibit  the  sending of acknowledges or retransmissions.  Imple-
  432. mentations of Source Quench entirely within the IP layer are usu-
  433. ally unsuccessful because IP lacks enough information to throttle
  434. a connection properly.  Holding back acknowledges tends  to  pro-
  435. duce  retransmissions and thus unnecessary traffic.  Holding back
  436. retransmissions may cause loss of a connection by  a  retransmis-
  437. sion  timeout.   Our  scheme  will  keep  connections alive under
  438. severe overload but at reduced bandwidth per connection.
  439.  
  440. Other protocols at the same layer as TCP should also  be  respon-
  441. sive  to  Source  Quench.  In each case we would suggest that new
  442. traffic should be throttled but acknowledges  should  be  treated
  443. normally.   The only serious problem comes from the User Datagram
  444. Protocol, not normally a major traffic generator.   We  have  not
  445. implemented  any  throttling  in  these protocols as yet; all are
  446. passed Source Quench messages by ICMP but ignore them.
  447.  
  448.                     Self-defense for gateways
  449.  
  450. As we have shown, gateways are vulnerable to  host  mismanagement
  451. of  congestion.  Host misbehavior by excessive traffic generation
  452. can prevent not only the host's own traffic from getting through,
  453. but  can interfere with other unrelated traffic.  The problem can
  454. be dealt with at the host level but since one malfunctioning host
  455. can  interfere  with others, future gateways should be capable of
  456. defending themselves against such behavior by obnoxious or  mali-
  457. cious hosts.  We offer some basic self-defense techniques.
  458.  
  459. On one occasion in late 1983, a TCP bug in an ARPANET host caused
  460. the  host  to  frantically  generate  retransmissions of the same
  461. datagram as fast as the ARPANET would accept them.   The  gateway
  462. ________
  463.   * This follows the control engineering dictum  "Never bother
  464.     with proportional control unless bang-bang  doesn't work".
  465.  
  466.  
  467. RFC 896    Congestion Control in IP/TCP Internetworks      1/6/84
  468.  
  469.  
  470. that connected our net with the ARPANET was saturated and  little
  471. useful  traffic  could  get  through,  since the gateway had more
  472. bandwidth to the ARPANET than to our  net.   The  gateway  busily
  473. sent  ICMP  Source  Quench  messages  but the malfunctioning host
  474. ignored them.  This continued for several hours, until  the  mal-
  475. functioning  host  crashed.   During this period, our network was
  476. effectively disconnected from the ARPANET.
  477.  
  478. When a gateway is forced to  discard  a  packet,  the  packet  is
  479. selected  at  the  discretion of the gateway.  Classic techniques
  480. for making  this  decision  are  to  discard  the  most  recently
  481. received packet, or the packet at the end of the longest outgoing
  482. queue.  We suggest that a worthwhile practical measure is to dis-
  483. card  the  latest  packet  from the host that originated the most
  484. packets currently queued within the gateway.  This strategy  will
  485. tend  to  balance throughput amongst the hosts using the gateway.
  486. We have not yet tried this strategy, but it  seems  a  reasonable
  487. starting point for gateway self-protection.
  488.  
  489. Another strategy is to discard a  newly  arrived  packet  if  the
  490. packet  duplicates  a  packet already in the queue.  The computa-
  491. tional load for this check is not a problem if hashing techniques
  492. are  used.   This  check will not protect against malicious hosts
  493. but will provide some protection against TCP implementations with
  494. poor  retransmission  control.   Gateways between fast local net-
  495. works and slower long-haul networks may find this check  valuable
  496. if the local hosts are tuned to work well with the local network.
  497.  
  498. Ideally  the  gateway  should  detect  malfunctioning  hosts  and
  499. squelch them; such detection is difficult in a pure datagram sys-
  500. tem.  Failure to  respond  to  an  ICMP  Source  Quench  message,
  501. though,  should be regarded as grounds for action by a gateway to
  502. disconnect a host.  Detecting such failure is non-trivial but  is
  503. a worthwhile area for further research.
  504.  
  505.                            Conclusion
  506.  
  507. The congestion control problems  associated  with  pure  datagram
  508. networks  are  difficult, but effective solutions exist.  If IP /
  509. TCP networks are to be operated under heavy load, TCP implementa-
  510. tions  must address several key issues in ways at least as effec-
  511. tive as the ones described here.
  512.  
  513.